package leetcode.tree;

public class Lc124 {
    int ans = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        if (root == null) return 0;
        getMaxPathSum(root);
        return ans;
    }
    private int getMaxPathSum(TreeNode node) {
        if (node == null) return 0;
        int leftVal = Math.max(getMaxPathSum(node.left),0);
        int rightVal = Math.max(getMaxPathSum(node.right),0);
        int sum = node.val + leftVal + rightVal;
        ans = Math.max(ans, sum);
        return node.val + Math.max(leftVal, rightVal);
    }
}
